from typing import List


class Solution:
    def maxFrequency(self, nums: List[int], k: int) -> int:
        nums.sort()
        size = len(nums)

        ans = 1

        j = 0
        now = 0
        for i in range(size):
            while j + 1 < size and now + (j - i + 1) * (nums[j + 1] - nums[j]) <= k:
                now += (j - i + 1) * (nums[j + 1] - nums[j])
                j += 1
            ans = max(ans, j - i + 1)
            now -= nums[j] - nums[i]

        return ans


if __name__ == "__main__":
    print(Solution().maxFrequency(nums=[1, 2, 4], k=5))  # 3
    print(Solution().maxFrequency(nums=[1, 4, 8, 13], k=5))  # 2
    print(Solution().maxFrequency(nums=[3, 9, 6], k=2))  # 1

    # 测试用例9 : 73
    print(Solution().maxFrequency(
        nums=[9930, 9923, 9983, 9997, 9934, 9952, 9945, 9914, 9985, 9982, 9970, 9932, 9985, 9902, 9975, 9990, 9922,
              9990, 9994, 9937, 9996, 9964, 9943, 9963, 9911, 9925, 9935, 9945, 9933, 9916, 9930, 9938, 10000, 9916,
              9911, 9959, 9957, 9907, 9913, 9916, 9993, 9930, 9975, 9924, 9988, 9923, 9910, 9925, 9977, 9981, 9927,
              9930, 9927, 9925, 9923, 9904, 9928, 9928, 9986, 9903, 9985, 9954, 9938, 9911, 9952, 9974, 9926, 9920,
              9972, 9983, 9973, 9917, 9995, 9973, 9977, 9947, 9936, 9975, 9954, 9932, 9964, 9972, 9935, 9946, 9966],
        k=3056))

    # 测试用例31 : 48
    print(Solution().maxFrequency(
        nums=[9953, 9960, 9908, 9957, 9919, 9967, 9941, 9985, 9925, 9933, 9989, 9999, 9928, 9990, 9973, 9930, 9982,
              9911, 9986, 9931, 9925, 9943, 9937, 9956, 9968, 9988, 9929, 9997, 9945, 9931, 9922, 9948, 9916, 9948,
              9998, 9967, 9945, 9906, 9914, 9947, 9997, 9945, 9923, 9969, 9903, 9947, 9938, 9972, 9969, 9953, 9926,
              9949, 9997, 9971, 9913, 9948, 9910, 9964, 9900, 9983, 9945, 9900, 9951, 9928, 9984, 9960, 9903, 9903,
              9983, 9920, 9909, 9927, 9987, 9994, 9987, 9965, 9941, 9921, 9914, 9936, 9979, 9917, 9965, 9906, 9942,
              9904, 9920, 9907, 9922, 9983, 9970, 9963, 9941, 9902, 9968, 9992, 9994, 9954, 9904, 9974, 9914, 9903,
              9934, 10000, 9991, 9991, 9986, 9965, 9980, 9907, 9911, 9918, 9993, 9981, 9986, 9986, 9944, 9973, 9918,
              9931, 9974, 9976, 9958, 9987, 9942, 9995, 9970, 9963, 9901, 9979, 9995, 9936, 9959, 9965, 9905, 9979,
              9927, 9989, 9926, 9984, 9956, 9936, 9931, 9954, 9901, 9949, 9943, 9945, 9966, 9973, 9931, 9970, 9916,
              9981, 9995, 9981, 9968, 9942, 9960, 10000, 9935, 9957, 9931, 9964, 9939, 9979, 9924, 9973, 9960, 9972,
              9915, 9981, 9993, 9961, 9963, 9970, 9917, 9955, 9993, 9930, 9972, 9940, 9921, 9978, 9915, 9988, 9904,
              9989, 9911, 9958, 9914, 9901, 9913, 9916, 9909, 9926, 9928, 9926, 9920, 9958, 9931, 9906, 9973, 9960,
              9909, 9948, 9983, 9948, 9936, 9953, 9974, 9940], k=410))
